package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

import org.junit.Test;

public class 射箭比赛最大得分20220924 {
	
	/**
	 * 二叉树直接 一次过
	 */
	public static int solution(int choice[],int index,int rest) {
		if(rest == 0)
			return 0;
		if(index == choice.length )
			return 0;
		
		int score1 = 0;
		int score2 = 0;
		if(rest >= choice[index] + 1)
			score1 = solution(choice,index + 1,rest - choice[index] - 1) + index;
		
		score2 = solution(choice,index + 1,rest);
		
		return Math.max(score1, score2);
		
	}
	
	@Test
	public void testsolution() {
//		int arr[] = {1,1,0,1,0,0,2,1,0,1,2,0};
		int arr[] = {0,0,0,0,0,0,0,0,0,0,0,100000};
		int rest = 100000;
		int ans = solution(arr,1,rest);
		System.out.println(ans);
		System.out.println(dp(arr,rest));
	}
	
	/**
	 * 直接 由上面的 递归 改成 dp
	 */
	public static int dp(int choice[],int target) {
		int len = choice.length;
		int dp [][] = new int [len + 1][target + 1];
		// 根据basecase 可以看出  这个 dp 表 就不需要初始化
		for(int  index = len - 1;index >= 0;index--) {
			for(int rest = 1;rest <= target ;rest++) {
				if(rest >= choice[index] + 1)
					dp[index][rest] = dp[index + 1][rest - choice[index] -1] + index;
				dp[index][rest] = Math.max(dp[index][rest], dp[index + 1][rest]);
			}
		}
		
		return dp[0][target];
	}
	

}
